﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0154_LeastInterval : IAlgorithm
    {
        // 任务调度器

        // 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，
        // 并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
        // 然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
        // 你需要计算完成所有任务所需要的 最短时间 。

        // 提示：
        //  1 <= task.length <= 10^4
        //  tasks[i] 是大写英文字母
        //  n 的取值范围为[0, 100]

        public void Test()
        {
            // 算法参数定义
            var task = new char[] { 'A', 'A', 'A', 'B', 'B', 'B' };
            // 算法执行与打印
            //Console.WriteLine(LeastInterval());
        }

        // 算法
        // (count[maxSize] - 1) * (n + 1) + maxCount
        public int LeastInterval(char[] tasks, int n)
        {
            var count = new int[26];
            foreach (var task in tasks)
                count[task - 'A']++;
            var maxSize = count.Max();
            var maxCount = 0;
            foreach (var item in count)
                if (item == maxSize)
                    maxCount++;
            var res = (maxSize - 1) * (n + 1) + maxCount;
            return Math.Max(res, tasks.Length);
        }
    }
}
